这道题我们先看一下数据范围:
显然复杂度和有关,既然如此,我们考虑用的复杂度来解决此题吧。(此题解法不止一种)
我们用表示在时刻发车(不管是第几次),所有在时刻之前到达的人的等待时间之和。表示第时刻有多少人开始等车,显然有:
我们再考虑一下边界条件,表示最先到的一个人来的时间,显然有。 表示最后一个人来的时间。最坏情况下,在最后一个人来的前一秒车开走了,那么总时间最多为。
最后,答案就是(最后一个人开始等车)。
然后,我们就可以用转移了。再看一下数据,得分。
优化1
转移时的复杂度体现在求和,这个可以用前缀和优化。
我们用表示前时刻等车的人数之和(与前文定义不同),表示前时刻到达的人如果从0时刻开始等车,他们的时间之和。
那么,就表示到这段时间里开始等车的人数之和,表示第时刻到第时刻来到的人,从时刻开始等车到他们来到的时间之和。就是到时刻来到的人从开始等车到上车的时间之和,这就是我们转移时求的东西,处理前缀可以转移。转移变为:
总复杂度,得分50。
优化2
我们对优化1的式子继续拆分,并将只与i有关的部分拿出提出来,得到:
熟悉的同学可能会看出,这就是一道斜率优化的板题了。
转移只与有关,我们考虑两个决策点,且优于,即:
移项得:
当时,。
当时,。
令,则原式变为:
或
我们就可以用单调队列维护斜率,可以证明,一定是一个下凸包(即单调递增),具体可以看一下网上斜率优化。
最后,转移实现,总复杂度,100分。
附上代码:
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 500;
const int MAXT = 4000000;
int n,m,x , Max_t;
int tot[ MAXT + 5 ] , sum[ MAXT + 5 ] , dp[ MAXT + 5 ];
int head = 1 , tail = 0;
int Queue[ MAXT + 5 ];
double delta_x( int u , int v ) {
return tot[ v ] - tot[ u ] == 0 ? 1e-9 : tot[ v ] - tot[ u ];
}
double delta_y( int u , int v ) {
return ( dp[ v ] + sum[ v ] ) - ( dp[ u ] + sum[ u ] );
}
double Slope( int u , int v ) {
return delta_y( u , v ) / delta_x( u , v );
}
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= n ; i ++ ) {
scanf("%d",&x);
Max_t = max( Max_t , x );
tot[ x ] ++ , sum[ x ] += x;
}
for( int i = 1 ; i <= Max_t + m - 1 ; i ++ ) {
tot[ i ] += tot[ i - 1 ];
sum[ i ] += sum[ i - 1 ];
}
for( int i = 0 ; i <= Max_t + m - 1 ; i ++ ) {
if( i >= m ) {
while( head < tail && Slope( Queue[ tail - 1 ] , Queue[ tail ] ) > Slope( Queue[ tail ] , i - m ) )
tail --;
Queue[ ++ tail ] = i - m;
}
while( head < tail && Slope( Queue[ head ] , Queue[ head + 1 ] ) <= i )
head ++;
dp[ i ] = tot[ i ] * i - sum[ i ];
if( head <= tail ) dp[ i ] = min( dp[ i ] , dp[ Queue[ head ] ] + ( tot[ i ] - tot[ Queue[ head ] ] ) * i - sum[ i ] + sum[ Queue[ head ] ] );
}
int Ans = 0x3f3f3f3f;
for( int i = Max_t ; i <= Max_t + m - 1 ; i ++ )
Ans = min( Ans , dp[ i ] );
printf("%d",Ans);
return 0;
}